package com.bo.day20241014;

import java.util.ArrayList;

/**
 * 给定一个二叉树的头节点head,返回这个二叉树的最大的二叉树搜索子树
 *
 * @Author: gpb
 * @Date: 2024/10/17 10:11
 * @Description:
 */
public class MaxSubBSTHead {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode (int value) {
            val = value;
        }
    }

    public static class Info {
        public boolean isBST;
        public int max;
        public int min;
        public TreeNode head;

        public TreeNode maxSubBSTHead;
        public int maxSubBSTSize;
        // 左神，左老师方法
        public Info (TreeNode h, int size, int mi, int ma) {
            maxSubBSTHead = h;
            maxSubBSTSize = size;
            min = mi;
            max = ma;
        }

        public Info (boolean isBST, int max, int min, TreeNode head) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
            this.head = head;
        }
    }

    public static TreeNode maxSubBSTHead (TreeNode head) {
        if (head == null) {
            return null;
        }
        return processIsI(head).head;
    }

    public static Info processIsI (TreeNode head) {
        if (head == null) {
            // 子节点不好处理返回null
            return null;
        }
        // 左右子树信息
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        // 最大值和最小值默认为当前节点值
        int max = head.val;
        int min = head.val;
        // 默认位空，如果是搜素二叉树就会有头节点，赋值
        TreeNode headNode = null;
        // 拿左树的信息
        if (leftInfo != null) {
            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);
            headNode = leftInfo.head;
        }
        if (rightInfo != null) {
            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
            if (head == null){
                head = rightInfo.head;
            }else {
                head = Math.max(head.val, rightInfo.head.val) == head.val ? head : rightInfo.head;
            }
        }
        // 默认是搜索二叉树
        boolean isBST = true;
        // 判断是否有为搜素二叉树
        // 左树不是搜索二叉树，这个树则不是搜索二叉树
        if (leftInfo != null && leftInfo.isBST) {
            isBST = false;
        }
        // 右树不是搜索二叉树，这个树则不是搜索二叉树
        if (rightInfo != null && !rightInfo.isBST) {
            isBST = false;
        }
        // 当前节点的值，比左右子树最大值小，比右子树最小值大，才是搜索二叉树
        if (leftInfo != null && leftInfo.max >= head.val) {
            isBST = false;
        }
        if (rightInfo != null && rightInfo.min <= head.val) {
            isBST = false;
        }
        // 如果是搜索二叉树，isBST为true赋值头街的
        if (isBST) {
            // 左树头节点和右树头节点取最大值
            TreeNode leftHead = leftInfo == null ? null : leftInfo.head;
            TreeNode rightHead = rightInfo == null ? null : rightInfo.head;
            headNode = leftHead != null ? (Math.max(leftHead.val, headNode.val) == leftHead.val ? leftHead : headNode) : headNode;
            headNode = rightHead != null ? (Math.max(rightHead.val, headNode.val) == rightHead.val ? rightHead : headNode) : headNode;
        }
        return new Info(isBST, max, min, headNode);
    }


    public static TreeNode maxSubBSTHead2 (TreeNode head) {
        if (head == null) {
            return null;
        }
        return process(head).maxSubBSTHead;
    }

    public static Info process (TreeNode X) {
        // 子节点不好处理返回null
        if (X == null) {
            return null;
        }
        Info leftInfo = process(X.left);
        Info rightInfo = process(X.right);
        int max = X.val;
        int min = X.val;
        TreeNode maxSubBSTHead = null;
        int maxSubBSTSize = 0;
        if (leftInfo != null) {
            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);
            maxSubBSTHead = leftInfo.maxSubBSTHead;
            maxSubBSTSize = leftInfo.maxSubBSTSize;
        }
        if (rightInfo != null) {
            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
            // 如果右树长度大于左树，则右树为最大搜索二叉树
            if (rightInfo.maxSubBSTSize > maxSubBSTSize) {
                maxSubBSTHead = rightInfo.maxSubBSTHead;
                maxSubBSTSize = rightInfo.maxSubBSTSize;
            }
        }
        // 判断是否是搜索二叉树
        // 左树为空，或者左树最大搜索二叉树头节点为当前节点，并且左树最大值小于当前节点值
        // 右树为空，或者右树最大搜索二叉树头节点为当前节点，并且右树最小值大于当前节点值
        // 如果是搜索二叉树，则更新最大搜索二叉树头节点和长度
        if ((leftInfo == null ? true : (leftInfo.maxSubBSTHead == X.left && leftInfo.max < X.val))
                && (rightInfo == null ? true : (rightInfo.maxSubBSTHead == X.right && rightInfo.min > X.val))) {
            maxSubBSTHead = X;
            maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubBSTSize) + (rightInfo == null ? 0 : rightInfo.maxSubBSTSize) + 1;
        }
        return new Info(maxSubBSTHead, maxSubBSTSize, min, max);
    }

    public static TreeNode maxSubBSTHead1 (TreeNode head) {
        if (head == null) {
            return null;
        }
        if (getBSTSize(head) != 0) {
            return head;
        }
        TreeNode leftAns = maxSubBSTHead1(head.left);
        TreeNode rightAns = maxSubBSTHead1(head.right);
        return getBSTSize(leftAns) >= getBSTSize(rightAns) ? leftAns : rightAns;
    }

    public static int getBSTSize (TreeNode head) {
        if (head == null) {
            return 0;
        }
        ArrayList<TreeNode> arr = new ArrayList<>();
        in(head, arr);
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i).val <= arr.get(i - 1).val) {
                return 0;
            }
        }
        return arr.size();
    }

    public static void in (TreeNode head, ArrayList<TreeNode> arr) {
        if (head == null) {
            return;
        }
        in(head.left, arr);
        arr.add(head);
        in(head.right, arr);
    }

    // for test
    public static TreeNode generateRandomBST (int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    // for test
    public static TreeNode generate (int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        TreeNode head = new TreeNode((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

    public static void main (String[] args) {
        int maxLevel = 4;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            TreeNode head = generateRandomBST(maxLevel, maxValue);
            if (maxSubBSTHead(head) != maxSubBSTHead1(head)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }

}
